<!DOCTYPE html>
<html lang="zh-cn">
<head>
    <title>容斥原理</title>
    <meta charset="utf-8" />
    <link rel="stylesheet" type="text/css" href="../../css/note.css" />
</head>
<body>

<p class="theorem">
	<b>容斥原理</b>
	设 `A, B` 为有限集, 则
	<span class="formula">
		`|A uu B| = |A| + |B| - |A nn B|`.
	</span>
</p>

<p class="corollary">
	设 `A_1, A_2, cdots, A_n` 为 `n` 个有限集, `n in ZZ^+`.
	`N = {1, 2, cdots, n}`, 则
	<span class="formula">
		`|uuu_(i=1)^n A_i| = sum_(C sube N) (-1)^(|C|-1)
		|nnn_(j in C) A_j|`
		`= sum_(k=1)^n (-1)^(k-1) sum_(1 le i_1 lt cdots lt i_k le n)
		|nnn_(j=1)^k A_(i_j)|`.
	</span>
	即 `n` 个集合的并集的基数, 等于它们每个集合的基数之和,
	减去每两个集合的交的基数之和, 加上每三个集合的交的基数之和,
	..., 最后加上 `(-1)^(n-1)` 乘以所有集合的交集的基数.
</p>

<p class="proof">
	`n = 1` 的情形是平凡的; `n = 2` 时, 即为容斥原理.
	设 `n-1` 时命题成立, 则 `n` 的情形, 由容斥原理,
	<span class="formula">
		左边
		`= |(uuu_(i=1)^(n-1) A_i) uu A_n|`
		`= |uuu_(i=1)^(n-1) A_i| + |A_n| - |uuu_(i=1)^(n-1) (A_i nn A_n)|`
		`= sum_(C sube N\\{n}) (-1)^(|C|-1) |nnn_(j in C) A_j| + |A_n|`
		`+ sum_(C sube N\\{n}) (-1)^|C| |nnn_(j in C) (A_j nn A_n)|`
		`=` 右边
	</span>
</p>

<p class="corollary">
	设 `A_1, A_2, cdots, A_n` 为 `n` 个基数相等的有限集, `n in ZZ^+`.
	`S_0 supe uuu_(i=1)^n A_i`, `S_k = nnn_(i=1)^k A_i`,
	`bar S_k = S_0 \\ S_k`, `k = 1, 2, cdots, n`. 则
	<span class="formula">
		`|nnn_(k=1)^n bar S_k| = sum_(k=0)^n (-1)^k (n;k) |S_k|`.
	</span>
</p>

<p class="proof">
	易知 `A_1, A_2, cdots, A_n` 中任意 `k` 个集合的交的基数都等于
	`|S_k|`, 而从 `n` 个集合中选出 `k` 个有 `(n;k)` 种选法, 所以
	<span class="formula">
		`|nnn_(k=1)^n bar S_k| = |S_0| - |uuu_(k=1)^n S_k|`
		`= |S_0| + sum_(k=1)^n (-1)^k (n;k) |S_k|`.
	</span>
</p>

<p class="example">
	<b>错排问题</b>
	有 `n` 封信和 `n` 只对应的信封, 有黑暗中随意将每封信装进一个信封,
	问恰好每封信都装错信封的装法有几种, 并求 `n to oo` 时,
	每封信都装错信封的概率.
</p>

<p class="solution">
	以集合 `S_k` 记所有使得前 `k` 封信被装进对的信封的安排, 则
	`|S_k| = (n-k)!`, `k = 1, 2, cdots, n`.
	所求的数为
	<span class="formula">
		`|nnn_(k=1)^n bar S_k|`
		`= sum_(k=0)^n (-1)^k (n;k) (n-k)!`
		`= sum_(k=0)^n (-1)^k (n!)/(k!)`.
	</span>
	`n to oo` 时, 所求概率为
	<span class="formula">
		`lim_(n to oo) 1/(n!) sum_(k=0)^n (-1)^k (n!)/(k!)`
		`= sum_(k=0)^oo (-1)^k/(k!) = "e"^-1`.
	</span>
</p>

<p class="example">
	<b>n 对夫妇问题</b>
	`n` 对夫妇坐成一横排, 问有几种坐法, 使得每一对夫妇的位置都不相邻.
</p>

<p class="solution">
	以集合 `S_k` 记所有使得前 `k` 对夫妇坐在一起的排列, 则这 `k`
	对夫妇两两 "合并", 后, 可以看作 `2n-k` 个人的全排列, 于是
	<span class="formula">
		`|S_k| = 2^k (2n - k)!`, `quad k = 1, 2, cdots, n`.
	</span>
	所求的数为
	<span class="formula">
		`|nnn_(k=1)^n bar S_k|`
		`= sum_(k=0)^n (n;k) (-2)^k (2n-k)!`.
	</span>
</p>

<p class="example">
  [群友 我是蒟蒻的泰博定理]
  设集合 `A` 有 `n` 个元素, 取 `A` 的子集满足真包含关系:
  <span class="formula">
    `A_1 sub A_2 sub cdots sub A_k`,
  </span>
  这样的取法有几种? 换言之, `A` 的全体子集按包含关系组成的偏序中, 长度为
  `k` 的链有几条?
</p>

<ol class="solution">
  <li>[群友 我是某用户的零壹叁]
    答案 `f(n, k)` 满足递推关系
    <span class="formula">
      `f(n, k) = {
        2^n, if k = 1;
        n!, if k = n+1;
        (k+1) f(n-1, k) + (k-1) f(n-1, k-1), otherwise;
      :}`
    </span>
    `k = 1` 时, 只要任取 `A` 的一个子集, 有 `2^n` 种取法;
    `k = n+1` 时, 相当于确定 `A` 的一个排列, 有 `n!` 种.<br>
    其它情况, 取定 `a in A`.
    满足题目条件的链中, 不含元素 `a` 的链有 `f(n-1, k)` 条.
    含有元素 `a` 的链, 我们将 `a` 去掉,
    剩余部分要么是 `n-1` 的集合上长为 `k` 的链, 要么是长为 `k-1`
    的链, 这是因为去掉 `a` 的操作可能破坏相邻两个集合的真包含关系.
    前者的取法有 `k f(n-1, k)` 种, 后者为 `(k-1) f(n-1, k-1)` 种.<br>
    从递推式可以得到特殊情况 `f(n, 2) = 3^n - 2^n`, `f(n, n) = (n+3)/2 n!`
    等等.
  </li>
  <li>`f(n, k)` 的显式表达式为
    <span class="formula">
      `f(n, k) = sum_(j=0)^(k-1) (-1)^j (k-1;j) (k-j+1)^n`.
    </span>
    我们考虑允许相等的子集链
    <span class="formula">
      `A_1 sube A_2 sube cdots sube A_k`,
    </span>
    这给出集合 `A` 的划分
    <span class="formula">
      `A_1, A_2 - A_1, A_3 - A_2, cdots, A - A_k`,
    </span>
    且 `A` 的每个元素都可以自由进入到任一划分, 因此这样的链共有
    `(k+1)^n` 条. 假如上面的链的 `k-1` 个 `sube` 符号中有 `j` 个取等,
    则此链相当于一个长度为 `k-j` 的允许相等的子集链, 共有 `(k-j+1)^n` 条.
    由容斥原理即得结论.
  </li>
  更详细的内容参见 <a href="http://oeis.org/A038719">oeis A038719</a>.
</ol>

<script src="../../js/note.js?type=math"></script>
</body>
</html>
